import numpy as np
# 计算一条最短路径
def dijkstra(adMatrix, origin, destination, unavailableNode, unavailableEdges):
    adjacentMatrix = np.array(adMatrix)
    size = len(adjacentMatrix)
    distance = np.zeros(size, dtype=float)  # 最短路长度
    flag = np.zeros(size)
    prev = np.zeros(size, dtype=int)
    route = []
    # 不能走的边
    if ( len(unavailableEdges) != 0):
        for p in unavailableEdges:
            for i in range(len(p) - 1):
                adjacentMatrix[p[i]][p[i + 1]] = np.inf
                adjacentMatrix[p[i + 1]][p[i]] = np.inf
    # 不能走的点
    if (len(unavailableNode) != 0):
        for n in unavailableNode:
            for i in range(len(adMatrix)):
                if (i != n):
                    adjacentMatrix[n][i] = np.inf
                    adjacentMatrix[i][n] = np.inf

    for i in range(size):
        distance[i] = adjacentMatrix[origin][i]
        flag[i] = 0
        if ((distance[i] < np.inf) & (distance[i] != 0)):
            prev[i] = origin
        else:
            prev[i] = -1
    flag[origin] = 1
    distance[origin] = 0
    now = origin
    for i in range(size):
        before = now
        min = np.inf
        for j in range(size):
            if ((flag[j] == 0) & (distance[j] < min)):
                min = distance[j]
                now = j
        if (now == before):
            break
        flag[now] = 1
        for j in range(size):
            if (flag[j] == 1):
                continue
            tmp = 0
            if (adjacentMatrix[now][j] == np.inf):
                tmp = np.inf
            else:
                tmp = min + adjacentMatrix[now][j]
            if (tmp < distance[j]):
                distance[j] = tmp
                prev[j] = now
    topPtr = destination
    if (prev[topPtr] == -1):
        return route
    route.append(topPtr)
    while (topPtr != origin):
        topPtr = prev[topPtr]
        route.append(topPtr)
    route = route[::-1]
    return route